{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.5 Sarsaで迷路を攻略"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 使用するパッケージの宣言\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/srv/conda/lib/python3.6/site-packages/matplotlib/cbook/deprecation.py:107: MatplotlibDeprecationWarning: Passing one of 'on', 'true', 'off', 'false' as a boolean is deprecated; use an actual boolean (True/False) instead.\n",
      "  warnings.warn(message, mplDeprecation, stacklevel=1)\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAASwAAAElCAYAAABect+9AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4wLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvFvnyVgAAGu1JREFUeJzt3XtUlHX+B/D3MzcEBoJfksJQoLlK8MtM0APaLzPYpFq7mXZgK4Ei/WmXk3TsuOtu222PmejR1V9HziqVrW5eUqFTrWwqrrcUvOCKlK55Q1uQIOQyMON8f3+MsILKDMQ8z3yH9+ucOR7m+c48n/kG777fZ57n+yhCCBARyUCndQFERO5iYBGRNBhYRCQNBhYRSYOBRUTSYGARkTQYWEQkDQYWEUmDgUVE0mBgEZE0DN1p3L9/fxEdHe2hUoioryotLb0ohAhz1a5bgRUdHY2SkpKeV0VEdB2Kopx2px2nhEQkDQYWEUmDgUVE0mBgEZE0GFhEJA0GFhFJg4FFRNJgYBGRNBhYRCQNBhYRSYOBRUTSYGARkTQYWEQkjW6t1uCthBCovFSJ0vOl2Fe5D8Wni1FeXY5mezPsDjsuOy5Dr9PDoDPA3+CP2LBYjIsah9GW0YiPiIclyAJFUbT+GETkgrSB5RAOfH3yayzcuxC7zuyC3WGHUW9EQ2sDHMJxTXu7ww67ww6r3YpdZ3dhz7k9MJvMaL3cCqPOiLG3jcWsxFlIHpwMncKBJ5E3ki6waptrsfLgSuTuycWl1ktoaG1o39Zsb3b7fRzCgfqWegCAFVZ8deIr7DyzE0GmIOQk5SDr7iyE+of2ev1E1HOKEMLtxgkJCUKrBfzO1Z/D7KLZ2FixETpFhyZbk8f2FWAMgEM48ETME3jvl+8hMjjSY/siIkBRlFIhRIKrdl4/9xFCYMXBFYhZGoN1R9fBard6NKwAoMnWBKvdirVH1yJmaQxWHFyB7gQ7EXmGVwdWZX0lxn80Hq98+QoabY2wC7uq+7cLOxptjXjly1cw/qPxqKyvVHX/RNSR1wZW/qF8xCyNwa6zu9Boa9S0lkZbI3ad3YWYZTHIP5SvaS1EfZnXBZYQAq9+9Spe/OJFNNgaYHeoO6q6EbvDjobWBrz4xYuY9bdZnCISacCrAuuy4zIyNmUg70Cex49T9VSTrQnLS5cjc3MmLjsua10OUZ/iNac1CCGQtTkL64+t99qwatNka8K68nUAgPxH83nSKZFKvGaENetvs7Dh2AavD6s2baGVsyVH61KI+gyvCKz8Q/nIO5Cn+cH17mqbHvJAPJE6NA+syvpKvPzFy9KMrDprsjXh5S9f5ikPRCrQNLCEEEj/LB3Wy1Yty/jZWuwt+PVnv+Y3h0QepmlgrTy0EqXnS73m1IWesjlsKDlfwqkhkYdpFljn6s+1n8HuCxptjXjlq1c4NSTyIM0Ca3bRbLTYW7TavUdY7VbMLpqtdRlEPkuTwKptrsXGio2qXxvoaXaHHZ9VfIba5lqtSyHySZoE1sqDK312kTydouOxLCIPUT01HMKB3D250p7G4EqTrQm5u3Ovu+opEf08qgfW1ye/xqXWS73/xo0APgewCMDbAN4H8BGAf13ZLgBsA7AAwDsA8gFU9X4ZAFDfWo+t32/1zJt7kerqasyYMQPR0dHw8/PDgAEDkJycjKKiIgDAZ599hgkTJiAsLAyKomD79u3aFuwDuupzm82G119/HcOHD0dgYCDCw8ORnp6OM2fOaF12r1H9WsKFexd2WNa413wKwAbgUQD/BWeAnQLQNpDbBWAPgMcA3AygGMDHAF4C4Ne7pTS0NiB3Ty5SBqf07ht7mUmTJqGpqQkrVqzAkCFDUFVVheLiYtTU1AAAGhsbMWbMGDz99NN49tlnNa7WN3TV501NTThw4AB++9vfYsSIEfjpp5+Qk5OD1NRUlJWVwWDwmkuHe0zVJZKFELhp3k29P8JqBvAegGcA3H69HQPIBTAawL1XnrPBOQp7AIDLhVm7L9gvGHWv1/nshdF1dXUIDQ1FUVERUlK6DuaLFy8iLCwM27Ztw3333adOgT6oO33epry8HHFxcSgrK8Odd97p4Qp7ziuXSK68VAmbw9b7b2y68vgWziDqrBZAAzqGmRFAFICzvV8OALRebsX5S+c98+ZewGw2w2w2o6CgAFar3FcqyKInfV5f77zRSmiob9xQRdXAKj1fCpPe1PtvrIdzqlcGYB6APwP4G4BzV7a3zUADO70u8KptvcykN6H0Qqln3twLGAwGfPjhh/jkk08QEhKCpKQkvPbaa/jmm2+0Ls1ndbfPW1tbkZOTg4kTJyIy0jdupKJqYO2r3OeZ41cAEAsgB0A6gCFwjpz+DGDHVW1UnJ01tjZiX+U+9XaogUmTJuH8+fMoLCzEgw8+iN27dyMxMRF//OMftS7NZ7nb53a7HU8//TTq6uqQn+87p9moegzrnpX3YNfZXT1+fbdtBnAYwAwASwFkA7Bctf0vAAIAPO6Z3d9z2z34R+Y/PPPmXur555/Hxx9/jIaGBphMztE0j2F5Vuc+t9vtSEtLw5EjR7B9+3YMHDhQ6xJd8spjWOXV5WruDggD4ABgvvL411XbbABOA7jVc7tX/fN6gdjYWNjtdh7XUtHVfW6z2fDUU0+hrKwM27ZtkyKsukPV7zm7c2fmbmkCsBbA3QAGwHmawnk4T2UYDKAfgEQ4p4f94TytYQecB+o9+MVJs81Dn9cL1NTUYPLkycjKysLw4cMRFBSEkpISzJ8/H8nJyQgODsaPP/6IM2fOoK6uDgBw4sQJhISEYODAgT73h6QGV30eEBCAJ598Evv370dhYSEURcEPP/wAALjpppvg7++v8Sf4+VQNLI8tI2MCEAngGwA/ArADCIYzjNpOYxgL56jqCzhPg4iE8zSIXj4H62oe+UbUS5jNZiQmJmLx4sU4ceIEWlpaYLFYkJ6ejrlz5wIACgoKkJmZ2f6a7OxsAMAbb7yBP/zhD1qULTVXfX7u3Dls3rwZABAfH9/htfn5+cjIyNCg6t6l6jEs3Zs6CPSdRe4UKHC8wUt0iFzxymNYep1ezd1prq99XiJPUzWwDDr5Lw3oDqPOqHUJRD5F1cDyN8h/0K87/I196/MSeZqqgRUbFqvm7jTX1z4vkaepGljjosb57MJ9nekVPcZFjdO6DCKfomp6jLaMhtlkVnOXmgk0BWK0ZbTWZRD5FFUDKz4iHq2XW9XcpWZaL7ciPjzedUMicpuqgWUJsvSZb85MehMigiK0LoPIp6gaWIqiYOxtY9XcpWbG3DrGZxfvI9KK6idGzUqchZ1ndvZsmZkdAI7AuUyMAsAfzstsWuG8njDkSruHAdwG5zLJuQAeQsdVRRfhP5fk+MO5WoMJzjXgAecaWTo4V3IAnKs8dKOnzCYzcpJy3H8BEblF9cBKHpyMIFNQ9wPrLIDvAEyDs+pGAJfhvGbwewC7Afy602uOwnnN4BFcuwzyVDgX8NsGZxA+AuB/r2zbBmeA9XAwGOwXjPsH3d+zFxPRDal+joFO0SEnKQcBxgDXja92Cc4RT1vEBsIZVl35J5xrttdfeVxPZBfbeiDAGICcpJw+c/oGkZo0+avKujur+/ftux3ATwCWwHk7r1Mu2v8E59QuEkAcnOF1PScAxHSvlK44hAOZIzJdNySibtMksEL9Q/F4zOMwKN2YkfrBOR2cCOfoah2Ag120/yecQQUA/41rA+sjAPMBnESvrYll0BnwRMwTCPX3jQX/ibyNZlcjz//lfBR8WwC7rRtrZOkADLryuAXO5Y/vvkHbI3Ae5yq78vMlADVwLt4HOI9hmQBsgvOYVWr36r+efoZ+mP/L+T//jYjoujQ70BIZHInFDy5GoLHzrWxu4CKcgdPmBwA3ddHWBudNKV698vgfXDvKMsIZVIfxnxuu9lCgMRCLUxfDEmxx3ZiIekTTI8NZI7KQEJHg3rIzrQA2wnkzif8DUA3gvhu0PYJrj0vdceX5zoLgnBLud6vk6zLqjBhlGcVjV0QepuqKo9dTWV+JmKUxaLB56PZfKjCbzKiYWcHRFVEPeeWKo9djCbZgyUNLun+ag5cIMAZgyYNLGFZEKtA8sAAgc0QmXhj5gnShFWgMxLT4aZwKEqnEKwILABZOWIgn73hSmtAKMAbgydgnkftArtalEPUZXhNYiqJg5aMrMTl2steHVoAxAJNjJ2PFIyt4gTORirwmsADnXWbyH83HtPhpXhtaAcYATI+fjvxH83lXHCKVeVVgAc6R1sIJC7H0oaUwm8xec6cdo84Is8mMpQ8tRe6EXI6siDTgdYHVJnNEJipmVmDsrWPdP7nUQwKNgRhz6xhUzKzgAXYiDXltYAHOUx62Td2GJQ8ucY62unPtYS8w6Awwm8xY8uASbJu6jacuEGnMqwMLcE4Rs+7OwrGZxzAlbgr6GfohwODZ41sBhgD0M/TDlNgpqJhZgay7szgFJPIC3nGAyA2RwZH4y6S/oLa5FvmH8rFg9wJcar3Us5VLb8BsMiPYFIycMTnIHJHJVReIvIzml+b0lEM4sPX7rcjdk4vdZ3ej9XIrTHoTGlob3FprS6foYDaZ21835tYxyEnKwf2D7ufie0Qqc/fSHGlGWJ3pFB1SBqcgZXAKhBA4f+k8Si+UYl/lPhSfLkZ5dTmabc2wOWy47LgMvU4Po84If6M/YsNiMS5qHEZbRiM+PB4RQRGc8hFJQNrAupqiKLAEW2AJtuCRYY9oXQ4ReQjnPkQkDQYWEUmDgUVE0mBgEZE0GFhEJA0GFhFJg4FFRNJgYBGRNBhYRCQNBhYRSYOBRUTSYGARkTR84uJnn8UVJLTTjWWXSD0cYRGRNDjC8mb8v7z6OKr1ahxhEZE0GFhEJA0GFhFJg4FFRNJgYBGRNBhYRCQNBhYRSYOBRUTSYGARkTQYWEQkDQYWEUmDgUVE0mBgEZE0GFhEJA0GFhFJg4FFRNJgYBGRNBhYRCQNBhYRSYOBRUTSYGARkTQYWEQkDQYWEUmDgUVE0mBgEZE0GFhEJA0GFhFJg4FFRNJgYBGRNBhYRCQNBhYRSYOBRUTSYGARkTQYWEQkDZ8JrOrqasyYMQPR0dHw8/PDgAEDkJycjKKiIgDA7373O8TExCAwMBChoaFITk7G7t27Na5abq76/GovvPACFEXBggULNKjUd7jq84yMDCiK0uGRmJiocdW9x6B1Ab1l0qRJaGpqwooVKzBkyBBUVVWhuLgYNTU1AIBhw4Zh2bJlGDRoEJqbm7Fo0SKkpqbi+PHjGDBggMbVy8lVn7dZv3499u/fj4iICI0q9R3u9HlKSgpWrVrV/rPJZNKiVM8QQrj9iI+PF96otrZWABBFRUVuv+ann34SAMRXX33lwcp8l7t9furUKRERESHKy8tFVFSUeP/991WqsIcA58MLudPnU6dOFQ8//LCKVfUOACXCjQzyiSmh2WyG2WxGQUEBrFary/atra3Iy8tDcHAwRowYoUKFvsedPrfb7UhLS8PcuXNxxx13qFyh73H393znzp245ZZbMHToUGRnZ6OqqkrFKj3MnVQTXj7CEkKI9evXi9DQUOHn5ycSExNFTk6O2Lt3b4c2hYWFIjAwUCiKIiIiIsQ333yjUbW+wVWf/+Y3vxG/+tWv2n/mCOvnc9Xna9asEZs3bxZlZWWioKBADB8+XMTFxQmr1aph1a7BzRGWzwSWEEI0NzeLLVu2iDfffFMkJSUJAOLdd99t397Q0CCOHz8u9uzZI7KyskRUVJQ4f/68hhXL70Z9vn37dhERESGqqqra2zKweoer3/OrVVZWCoPBIDZs2KByld3TJwOrs+eee04YjUbR0tJy3e1DhgwRb731lspV+ba2Pp8zZ45QFEXo9fr2BwCh0+mExWLRuswbkyCwOnP1ex4dHS3mzZunclXd425g+cy3hNcTGxsLu90Oq9V63W9KHA4HWlpaNKjMd7X1+fTp05Gent5h24QJE5CWlobs7GyNqvNNXf2eX7x4EZWVlQgPD9eout7lE4FVU1ODyZMnIysrC8OHD0dQUBBKSkowf/58JCcnAwDmzp2LiRMnIjw8HNXV1Vi2bBnOnTuHKVOmaFy9nFz1+W233XbNa4xGIwYOHIhhw4ZpULH8XPW5TqfDa6+9hkmTJiE8PBynTp3CnDlzcMstt+Dxxx/Xuvxe4ROBZTabkZiYiMWLF+PEiRNoaWmBxWJBeno65s6dC4PBgKNHj2LlypWoqanBzTffjFGjRmHHjh0YPny41uVLyVWfU+9z1ed6vR5HjhzBxx9/jLq6OoSHh2P8+PFYu3YtgoKCtC6/VyjO6aN7EhISRElJiQfLIdKYojj/7cbfBf18iqKUCiESXLXzifOwiKhvYGARkTQYWEQkDQYWEUmDgUVE0mBgEZE0GFhEJA0GFhFJg4FFRNJgYBGRNBhYRCQNBhYRSYOBRUTSYGARkTQYWEQkDQYWEUmDgUVE0mBgEZE0GFhEJA0GFhFJg4FFRNJgYBGRNBhYRCQNBhYRSYOBRUTSYGARkTQYWEQkDQYWEUmDgUVE0mBgEZE0GFhEJA0GFhFJg4FFRNJgYBGRNBhYRCQNBhYRSYOBRUTSYGARkTQYWEQkDQYWEUmDgUVE0mBgEZE0GFhEJA2D1gVQFxTF+a8Q2tbRF7X1PXkVjrCISBocYRFdjaNZbbg5ouUIi4ikwcAiImkwsIhIGgwsIpIGA4uIpMHAIiJpMLCISBoMLCKSBgOLiKTBwCIiaTCwiEgaDCwikgYDi4ikwcAiImkwsIhIGgwsIpIGA4uIpMHAIiJpMLCISBoMLCKSBgOLiKTBwCIiaTCwiEgaDCwikgYDi4ikwcAiImkwsIhIGgwsIpIGA4uIpMHAIiJpMLCISBoMLCKSBgOLiKThM4FVXV2NGTNmIDo6Gn5+fhgwYACSk5NRVFTU3ua7777DE088gZCQEAQEBGDkyJE4duyYhlXLzVWfK4py3cfMmTM1rlxervq8oaEBL730EiIjI+Hv749hw4Zh0aJFGlfdewxaF9BbJk2ahKamJqxYsQJDhgxBVVUViouLUVNTAwD4/vvvMXbsWDz77LPYunUrQkJCUFFRAbPZrHHl8nLV5xcuXOjQvqSkBBMnTsSUKVO0KNcnuOrzWbNm4e9//ztWrVqFQYMGYceOHcjOzkb//v3xzDPPaFx9LxBCuP2Ij48X3qi2tlYAEEVFRTdsk5aWJtLT01WsqhcAzocXcqfPO3v++efF0KFDPViVb3Onz+Pi4sTvf//7Ds/de++9YubMmZ4u72cBUCLcyCCfmBKazWaYzWYUFBTAarVes93hcKCwsBCxsbFITU1FWFgYRo0ahU8//VSDan2Dqz7vrKGhAX/961+RnZ2tQnW+yZ0+v+eee1BYWIizZ88CAHbv3o1Dhw4hNTVVzVI9x51UE14+whJCiPXr14vQ0FDh5+cnEhMTRU5Ojti7d68QQogLFy4IACIgIEDk5uaKgwcPitzcXKHX60VhYaHGlXfBi0dYQnTd550tX75cGI1GUVVVpXKVvsVVn7e0tIjMzEwBQBgMBmEwGMQHH3ygYcXugZsjLJ8JLCGEaG5uFlu2bBFvvvmmSEpKEgDEu+++KyorKwUAkZaW1qF9WlqaSE1N1ahaN3h5YAlx4z7vLCEhQUyePFmDCn1PV32+YMECMXToUFFQUCAOHz4s/vSnP4nAwEDx5Zdfalx11/pkYHX23HPPCaPRKFpaWoTBYBBvv/12h+1vvfWWiI2N1ag6N0gQWJ1d3edtDh48KACILVu2aFiZ72rr87q6OmE0GsWmTZuu2Z6cnKxRde5xN7B84hjWjcTGxsJut8NqtWLUqFH49ttvO2z/7rvvEBUVpVF1vunqPm+Tl5eH6OhopKSkaFiZ72rrc0VRYLPZoNfrO2zX6/VwOBwaVdfL3Ek14eUjrIsXL4rx48eLVatWicOHD4uTJ0+KtWvXigEDBoiUlBQhhBAbN24URqNRLF++XBw/flzk5eUJg8EgPv/8c42r74IXj7Dc6XMhhGhsbBTBwcHinXfe0bBa3+BOn48bN07ExcWJbdu2iZMnT4r8/HzRr18/sWTJEo2r7xr60pTQarWKOXPmiISEBBESEiL8/f3FkCFDxKuvvipqamra2+Xn54tf/OIXol+/fuLOO+8Uq1ev1rBqN3hxYLnb5ytXrhR6vV5UVlZqWK1vcKfPL1y4IDIyMkRERITo16+fGDZsmHj//feFw+HQuPquuRtYirOtexISEkRJSYnHRnvUiaI4/+3GfyMiGSmKUiqESHDVzqePYRGRb2FgEZE0GFhEJA0GFhFJg4FFRNJgYBGRNBhYRCQNBhYRSYOBRUTSYGAReal///vfSE9Px+DBgxEfH4+kpCRs3LgRALBz506MHj0aMTExiImJQV5e3jWvv+uuu5CWltbhuYyMDKxfv16V+j3BZ9Z0J/IlQgg89thjmDp1KlavXg0AOH36NAoKCvDDDz8gPT0dmzZtwsiRI3Hx4kVMmDABFosFDz/8MADg2LFjcDgc2LFjBxobGxEYGKjlx+k1HGEReaGtW7fCZDJh+vTp7c9FRUXhpZdewrJly5CRkYGRI0cCAPr374/58+dj3rx57W1Xr16NZ555Bg888AAKCgpUr99TGFhEXujo0aPtgXS9bfHx8R2eS0hIwNGjR9t//vTTT/HUU08hLS0Na9as8WitamJgEUlg5syZuOuuuzBq1CjnMittK3lcpe25/fv3IywsDFFRUUhOTsaBAwdQW1urdskewcAi8kJxcXE4cOBA+8/Lli3D119/jerqasTFxaHzMk+lpaWIjY0FAKxZswYVFRWIjo7G7bffjvr6emzYsEHV+j2FgUXkhe6//35YrVZ88MEH7c81NTUBcI62PvzwQxw6dAgAUFNTg9dffx2zZ8+Gw+HAunXrUFZWhlOnTuHUqVPYvHmzz0wLGVhEXkhRFGzatAnFxcUYNGgQRo8ejalTp+K9995DeHg4PvnkE2RnZyMmJgZjxoxBVlYWJk6ciB07dsBiscBisbS/17333ovy8vL2O3FPmzYNkZGRiIyMRFJSklYfsUe44qg344qj1EdwxVEi8jkMLCKSBgOLiKTBwCIiaTCwiEgaDCwikgYDi4ikwcAiImkwsIhIGgwsIpIGA4uIpMHAIiJpMLCISBoMLCKSBgOLiKTBwCIiaTCwiEgaDCwikgYDi4ikwcAiImkwsIhIGgwsIpIGA4uIpMHAIiJpMLCISBoMLCKSRrduVa8oSjWA054rh4j6qCghRJirRt0KLCIiLXFKSETSYGARkTQYWEQkDQYWEUmDgUVE0mBgEZE0GFhEJA0GFhFJg4FFRNL4f/+izvyQK8sjAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 360x360 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# 初期位置での迷路の様子\n",
    "\n",
    "# 図を描く大きさと、図の変数名を宣言\n",
    "fig = plt.figure(figsize=(5, 5))\n",
    "ax = plt.gca()\n",
    "\n",
    "# 赤い壁を描く\n",
    "plt.plot([1, 1], [0, 1], color='red', linewidth=2)\n",
    "plt.plot([1, 2], [2, 2], color='red', linewidth=2)\n",
    "plt.plot([2, 2], [2, 1], color='red', linewidth=2)\n",
    "plt.plot([2, 3], [1, 1], color='red', linewidth=2)\n",
    "\n",
    "# 状態を示す文字S0～S8を描く\n",
    "plt.text(0.5, 2.5, 'S0', size=14, ha='center')\n",
    "plt.text(1.5, 2.5, 'S1', size=14, ha='center')\n",
    "plt.text(2.5, 2.5, 'S2', size=14, ha='center')\n",
    "plt.text(0.5, 1.5, 'S3', size=14, ha='center')\n",
    "plt.text(1.5, 1.5, 'S4', size=14, ha='center')\n",
    "plt.text(2.5, 1.5, 'S5', size=14, ha='center')\n",
    "plt.text(0.5, 0.5, 'S6', size=14, ha='center')\n",
    "plt.text(1.5, 0.5, 'S7', size=14, ha='center')\n",
    "plt.text(2.5, 0.5, 'S8', size=14, ha='center')\n",
    "plt.text(0.5, 2.3, 'START', ha='center')\n",
    "plt.text(2.5, 0.3, 'GOAL', ha='center')\n",
    "\n",
    "# 描画範囲の設定と目盛りを消す設定\n",
    "ax.set_xlim(0, 3)\n",
    "ax.set_ylim(0, 3)\n",
    "plt.tick_params(axis='both', which='both', bottom='off', top='off',\n",
    "                labelbottom='off', right='off', left='off', labelleft='off')\n",
    "\n",
    "# 現在地S0に緑丸を描画する\n",
    "line, = ax.plot([0.5], [2.5], marker=\"o\", color='g', markersize=60)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 初期の方策を決定するパラメータtheta_0を設定\n",
    "\n",
    "# 行は状態0～7、列は移動方向で↑、→、↓、←を表す\n",
    "theta_0 = np.array([[np.nan, 1, 1, np.nan],  # s0\n",
    "                    [np.nan, 1, np.nan, 1],  # s1\n",
    "                    [np.nan, np.nan, 1, 1],  # s2\n",
    "                    [1, 1, 1, np.nan],  # s3\n",
    "                    [np.nan, np.nan, 1, 1],  # s4\n",
    "                    [1, np.nan, np.nan, np.nan],  # s5\n",
    "                    [1, np.nan, np.nan, np.nan],  # s6\n",
    "                    [1, 1, np.nan, np.nan],  # s7、※s8はゴールなので、方策はなし\n",
    "                    ])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 方策パラメータtheta_0をランダム方策piに変換する関数の定義\n",
    "\n",
    "\n",
    "def simple_convert_into_pi_from_theta(theta):\n",
    "    '''単純に割合を計算する'''\n",
    "\n",
    "    [m, n] = theta.shape  # thetaの行列サイズを取得\n",
    "    pi = np.zeros((m, n))\n",
    "    for i in range(0, m):\n",
    "        pi[i, :] = theta[i, :] / np.nansum(theta[i, :])  # 割合の計算\n",
    "\n",
    "    pi = np.nan_to_num(pi)  # nanを0に変換\n",
    "\n",
    "    return pi\n",
    "\n",
    "# ランダム行動方策pi_0を求める\n",
    "pi_0 = simple_convert_into_pi_from_theta(theta_0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 初期の行動価値関数Qを設定\n",
    "\n",
    "[a, b] = theta_0.shape  # 行と列の数をa, bに格納\n",
    "Q = np.random.rand(a, b) * theta_0\n",
    "# * theta0をすることで要素ごとに掛け算をし、Qの壁方向の値がnanになる\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ε-greedy法を実装\n",
    "\n",
    "\n",
    "def get_action(s, Q, epsilon, pi_0):\n",
    "    direction = [\"up\", \"right\", \"down\", \"left\"]\n",
    "\n",
    "    # 行動を決める\n",
    "    if np.random.rand() < epsilon:\n",
    "        # εの確率でランダムに動く\n",
    "        next_direction = np.random.choice(direction, p=pi_0[s, :])\n",
    "    else:\n",
    "        # Qの最大値の行動を採用する\n",
    "        next_direction = direction[np.nanargmax(Q[s, :])]\n",
    "\n",
    "    # 行動をindexに\n",
    "    if next_direction == \"up\":\n",
    "        action = 0\n",
    "    elif next_direction == \"right\":\n",
    "        action = 1\n",
    "    elif next_direction == \"down\":\n",
    "        action = 2\n",
    "    elif next_direction == \"left\":\n",
    "        action = 3\n",
    "\n",
    "    return action\n",
    "\n",
    "\n",
    "def get_s_next(s, a, Q, epsilon, pi_0):\n",
    "    direction = [\"up\", \"right\", \"down\", \"left\"]\n",
    "    next_direction = direction[a]  # 行動aの方向\n",
    "\n",
    "    # 行動から次の状態を決める\n",
    "    if next_direction == \"up\":\n",
    "        s_next = s - 3  # 上に移動するときは状態の数字が3小さくなる\n",
    "    elif next_direction == \"right\":\n",
    "        s_next = s + 1  # 右に移動するときは状態の数字が1大きくなる\n",
    "    elif next_direction == \"down\":\n",
    "        s_next = s + 3  # 下に移動するときは状態の数字が3大きくなる\n",
    "    elif next_direction == \"left\":\n",
    "        s_next = s - 1  # 左に移動するときは状態の数字が1小さくなる\n",
    "\n",
    "    return s_next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Sarsaによる行動価値関数Qの更新\n",
    "\n",
    "\n",
    "def Sarsa(s, a, r, s_next, a_next, Q, eta, gamma):\n",
    "\n",
    "    if s_next == 8:  # ゴールした場合\n",
    "        Q[s, a] = Q[s, a] + eta * (r - Q[s, a])\n",
    "\n",
    "    else:\n",
    "        Q[s, a] = Q[s, a] + eta * (r + gamma * Q[s_next, a_next] - Q[s, a])\n",
    "\n",
    "    return Q\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Sarsaで迷路を解く関数の定義、状態と行動の履歴および更新したQを出力\n",
    "\n",
    "\n",
    "def goal_maze_ret_s_a_Q(Q, epsilon, eta, gamma, pi):\n",
    "    s = 0  # スタート地点\n",
    "    a = a_next = get_action(s, Q, epsilon, pi)  # 初期の行動\n",
    "    s_a_history = [[0, np.nan]]  # エージェントの移動を記録するリスト\n",
    "\n",
    "    while (1):  # ゴールするまでループ\n",
    "        a = a_next  # 行動更新\n",
    "\n",
    "        s_a_history[-1][1] = a\n",
    "        # 現在の状態（つまり一番最後なのでindex=-1）に行動を代入\n",
    "\n",
    "        s_next = get_s_next(s, a, Q, epsilon, pi)\n",
    "        # 次の状態を格納\n",
    "\n",
    "        s_a_history.append([s_next, np.nan])\n",
    "        # 次の状態を代入。行動はまだ分からないのでnanにしておく\n",
    "\n",
    "        # 報酬を与え,　次の行動を求めます\n",
    "        if s_next == 8:\n",
    "            r = 1  # ゴールにたどり着いたなら報酬を与える\n",
    "            a_next = np.nan\n",
    "        else:\n",
    "            r = 0\n",
    "            a_next = get_action(s_next, Q, epsilon, pi)\n",
    "            # 次の行動a_nextを求めます。\n",
    "\n",
    "        # 価値関数を更新\n",
    "        Q = Sarsa(s, a, r, s_next, a_next, Q, eta, gamma)\n",
    "\n",
    "        # 終了判定\n",
    "        if s_next == 8:  # ゴール地点なら終了\n",
    "            break\n",
    "        else:\n",
    "            s = s_next\n",
    "\n",
    "    return [s_a_history, Q]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "エピソード:1\n",
      "1.740397889068286\n",
      "迷路を解くのにかかったステップ数は340です\n",
      "エピソード:2\n",
      "0.13503458373686233\n",
      "迷路を解くのにかかったステップ数は22です\n",
      "エピソード:3\n",
      "0.09246907428716789\n",
      "迷路を解くのにかかったステップ数は16です\n",
      "エピソード:4\n",
      "0.5063317503848415\n",
      "迷路を解くのにかかったステップ数は196です\n",
      "エピソード:5\n",
      "0.05687631793450576\n",
      "迷路を解くのにかかったステップ数は6です\n",
      "エピソード:6\n",
      "0.04893807621655272\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:7\n",
      "0.04834899787371577\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:8\n",
      "0.04761908880205956\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:9\n",
      "0.04677645290000576\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:10\n",
      "0.045843864856086325\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:11\n",
      "0.04483983782974399\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:12\n",
      "0.043779485479883695\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:13\n",
      "0.042675215047680126\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:14\n",
      "0.04153728211886826\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:15\n",
      "0.040374232555446865\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:16\n",
      "0.03919325275759161\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:17\n",
      "0.038000445773695934\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:18\n",
      "0.03680104771690318\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:19\n",
      "0.03559959638219756\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:20\n",
      "0.034400061813603666\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:21\n",
      "0.033205946781860396\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:22\n",
      "0.03202036364401195\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:23\n",
      "0.03084609282070938\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:24\n",
      "0.029685627104656054\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:25\n",
      "0.028541205170473705\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:26\n",
      "0.027414836963429445\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:27\n",
      "0.026308323077353646\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:28\n",
      "0.02522326976994238\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:29\n",
      "0.02416110088886625\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:30\n",
      "0.023123067679855835\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:31\n",
      "0.02211025720569093\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:32\n",
      "0.021123599912263313\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:33\n",
      "0.02016387672576392\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:34\n",
      "0.01923172594619238\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:35\n",
      "0.018327650110585236\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:36\n",
      "0.017452022929504207\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:37\n",
      "0.016605096348093484\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:38\n",
      "0.01578700774491637\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:39\n",
      "0.014997787254843464\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:40\n",
      "0.01423736518413643\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:41\n",
      "0.013505579474543006\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:42\n",
      "0.012802183167136438\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:43\n",
      "0.012126851814450945\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:44\n",
      "0.01147919079019566\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:45\n",
      "0.010858742448595304\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:46\n",
      "0.010264993089572627\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:47\n",
      "0.009697379691037566\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:48\n",
      "0.009155296375068955\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:49\n",
      "0.008638100580476205\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:50\n",
      "0.008145118919875904\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:51\n",
      "0.0076756527048501555\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:52\n",
      "0.007228983127849586\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:53\n",
      "0.0068043760941947085\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:54\n",
      "0.006401086701764314\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:55\n",
      "0.00601836336972239\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:56\n",
      "0.005655451620915519\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:57\n",
      "0.005311597525389122\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:58\n",
      "0.004986050814833831\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:59\n",
      "0.004678067679725784\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:60\n",
      "0.004386913262472203\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:61\n",
      "0.0041118638610803115\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:62\n",
      "0.0038522088587423786\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:63\n",
      "0.0036072523953228908\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:64\n",
      "0.003376314797076563\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:65\n",
      "0.003158733781044365\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:66\n",
      "0.002953865450508353\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:67\n",
      "0.0027610850976586\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:68\n",
      "0.0025797878292634913\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:69\n",
      "0.0024093890306668975\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:70\n",
      "0.0022493246828743096\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:71\n",
      "0.0020990515468650717\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:72\n",
      "0.001958047228589721\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:73\n",
      "0.001825810137400019\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:74\n",
      "0.0017018593499183998\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:75\n",
      "0.001585734390612048\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:76\n",
      "0.0014769949395799786\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:77\n",
      "0.0013752204773278542\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:78\n",
      "0.0012800098755648692\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:79\n",
      "0.0011909809423544804\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:80\n",
      "0.001107769929260427\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:81\n",
      "0.001030031007467569\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:82\n",
      "0.0009574357192249083\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:83\n",
      "0.0008896724103616416\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:84\n",
      "0.0008264456490566507\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:85\n",
      "0.0007674756355071644\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:86\n",
      "0.0007124976066410493\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:87\n",
      "0.0006612612395541229\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:88\n",
      "0.0006135300569117819\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:89\n",
      "0.0005690808371591194\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:90\n",
      "0.0005277030320034459\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:91\n",
      "0.0004891981933030642\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:92\n",
      "0.0004533794111698519\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:93\n",
      "0.0004200707648208679\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:94\n",
      "0.00038910678744408234\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:95\n",
      "0.00036033194611395647\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:96\n",
      "0.0003336001375814357\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:97\n",
      "0.0003087742005674077\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:98\n",
      "0.0002857254450225888\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:99\n",
      "0.0002643331986663666\n",
      "迷路を解くのにかかったステップ数は4です\n",
      "エピソード:100\n",
      "0.00024448437097635\n",
      "迷路を解くのにかかったステップ数は4です\n"
     ]
    }
   ],
   "source": [
    "# Sarsaで迷路を解く\n",
    "\n",
    "eta = 0.1  # 学習率\n",
    "gamma = 0.9  # 時間割引率\n",
    "epsilon = 0.5  # ε-greedy法の初期値\n",
    "v = np.nanmax(Q, axis=1)  # 状態ごとに価値の最大値を求める\n",
    "is_continue = True\n",
    "episode = 1\n",
    "\n",
    "while is_continue:  # is_continueがFalseになるまで繰り返す\n",
    "    print(\"エピソード:\" + str(episode))\n",
    "\n",
    "    # ε-greedyの値を少しずつ小さくする\n",
    "    epsilon = epsilon / 2\n",
    "\n",
    "    # Sarsaで迷路を解き、移動した履歴と更新したQを求める\n",
    "    [s_a_history, Q] = goal_maze_ret_s_a_Q(Q, epsilon, eta, gamma, pi_0)\n",
    "\n",
    "    # 状態価値の変化\n",
    "    new_v = np.nanmax(Q, axis=1)  # 状態ごとに価値の最大値を求める\n",
    "    print(np.sum(np.abs(new_v - v)))  # 状態価値の変化を出力\n",
    "    v = new_v\n",
    "\n",
    "    print(\"迷路を解くのにかかったステップ数は\" + str(len(s_a_history) - 1) + \"です\")\n",
    "\n",
    "    # 100エピソード繰り返す\n",
    "    episode = episode + 1\n",
    "    if episode > 100:\n",
    "        break\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
